// @algorithm @lc id=583 lang=cpp 
// @title delete-operation-for-two-strings


// @test("sea","eat")=2
// @test("leetcode","etco")=4
class Solution {
public:
    int minDistance(string word1, string word2) {
        int m = word1.size(), n = word2.size();
        if(m==0 || n==0) return abs(m-n);
        vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
        for(int i=1; i<=m; i++) dp[i][0] = i;
        for(int j=1; j<=n; j++) dp[0][j] = j;
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++)
                dp[i+1][j+1] = word1[i]==word2[j] ? dp[i][j]
                        : 1 + min(dp[i][j+1], dp[i+1][j]);
        }
        return dp[m][n];
    }
};